#define _CRT_SECURE_NO_WARNINGS 1



//#include <stdbool.h>
//
//struct ListNode
//{
//	int val;
//	struct ListNode* next;
//};
//
//bool hasCycle(struct ListNode* head)
//{
//	struct ListNode* fast, * slow;
//	fast = slow = head;
//
//	while (fast && fast->next)
//	{
//		slow = slow->next;
//		fast = fast->next->next;
//
//		if (slow == fast)
//		{
//			return true;
//		}
//	}
//
//	return false;
//}




//#include <stdio.h>
//
//struct ListNode
//{
//	int val;
//	struct ListNode* next;
//};
//
//struct ListNode* detectCycle(struct ListNode* head)
//{
//	struct ListNode* fast, * slow;
//	fast = slow = head;
//
//	while (fast && fast->next)
//	{
//		slow = slow->next;
//		fast = fast->next->next;
//
//		if (slow == fast)
//		{
//			struct ListNode* meet = slow;
//
//			while (head != meet)
//			{
//				meet = meet->next;
//				head = head->next;
//			}
//
//			return meet;
//		}
//	}
//
//	return NULL;
//}




#include <stdio.h>
#include <stdlib.h>

struct Node
{
	int val;
	struct Node *next;
	struct Node *random;
};


struct Node* copyRandomList(struct Node* head)
{
	struct Node* cur = head;

	while (cur)
	{
		struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
		copy->val = cur->val;
		copy->next = cur->next;
		cur->next = copy;
		cur = cur->next->next;
	}

	cur = head;

	while (cur)
	{
		struct Node* copy = cur->next;
		
		if (NULL == cur->random)
		{
			copy->random = NULL;
		}
		else
		{
			copy->random = cur->random->next;
		}

		cur = cur->next->next;
	}

	cur = head;
	struct Node* copyhead, * tail;
	copyhead = tail = NULL;

	while (cur)
	{
		struct Node* copy = cur->next;

		if (NULL == copyhead)
		{
			copyhead = tail = copy;
		}
		else
		{
			tail->next = copy;
			tail = tail->next;
		}

		cur->next = copy->next;
		cur = cur->next;
	}

	return copyhead;
}